#include <stdio.h>
#include <stdlib.h>
//图的应用之拓扑排序(有向图)
#define MAXSIZE 100
//图的邻接矩阵的声明
typedef struct 
{
    int vertex[MAXSIZE];
    int edge[MAXSIZE][MAXSIZE];
    int vertex_num;
    int edge_num;
}mat_graph;
//图的邻接表:顶点头节点+边节点
//①边节点的声明
typedef struct Edgenode
{
    int edge_ver;
    struct Edgenode *next;
}edgenode;
//②顶点头节点的声明
typedef struct 
{
    int in; //存储该顶点的入度
    int data;
    edgenode *head; //嵌套结构体
}vertexnode;
//③邻接表的声明
typedef struct 
{
    vertexnode *adj_list;  //把所有顶点集合成数组
    int vertex_num;
    int edge_num;
}adj_graph;
void creatgraph(mat_graph *g)
{
    g->vertex_num=14;
    g->edge_num=20;
    int i,j;
    for(i=0;i<g->vertex_num;i++)
    {
        g->vertex[i]=i;
    }
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<g->vertex_num;j++)
        {
            g->edge[i][j]=0;
        }
    }
    g->edge[0][4]=1;
    g->edge[0][5]=1;
    g->edge[0][11]=1;
    g->edge[1][2]=1;
    g->edge[1][4]=1;
    g->edge[1][8]=1;
    g->edge[2][5]=1;
    g->edge[2][6]=1;
    g->edge[2][9]=1;
    g->edge[3][2]=1;
    g->edge[3][13]=1;
    g->edge[4][7]=1;
    g->edge[5][8]=1;
    g->edge[5][12]=1;
    g->edge[6][5]=1;
    g->edge[8][7]=1;
    g->edge[9][10]=1;
    g->edge[9][11]=1;
    g->edge[10][13]=1;
    g->edge[12][9]=1;
}
//把邻接矩阵转换成邻接表
void creatadjgraph(mat_graph *g,adj_graph **adj)
{
    edgenode *e;
    int i,j;
    *adj=(adj_graph *)malloc(sizeof(adj_graph));
    (*adj)->adj_list=(vertexnode *)malloc(sizeof(vertexnode)*MAXSIZE);
    for(i=0;i<g->vertex_num;i++)
    {
        (*adj)->adj_list[i].in=0;
        (*adj)->adj_list[i].data=g->vertex[i];
        (*adj)->adj_list[i].head=NULL;
    }
    (*adj)->vertex_num=g->vertex_num;
    (*adj)->edge_num=g->edge_num;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<g->vertex_num;j++)
        {
            if(g->edge[i][j]==1)
            {
                e=(edgenode *)malloc(sizeof(edgenode));
                (*adj)->adj_list[j].in++;
                e->next=(*adj)->adj_list[i].head;//头插法
                e->edge_ver=(*adj)->adj_list[j].data; 
                (*adj)->adj_list[i].head=e;
            }
        }
    }
}
//拓扑排序
int stack[MAXSIZE]={0}; //用数组形式表示栈
int top=-1;
void aov(adj_graph *adj)
{
    int i,k;
    for(i=0;i<adj->vertex_num;i++)
    {
        if(adj->adj_list[i].in==0)
        {
            top++;
            stack[top]=adj->adj_list[i].data;
        }
    }
    edgenode *e;
    while(top!=-1)
    {
        k=stack[top];
        top--;
        printf("V%d->",k);
        e=adj->adj_list[k].head;
        while(e!=NULL)
        {
            i=e->edge_ver;
            adj->adj_list[i].in--;
            if(adj->adj_list[i].in==0)
            {
                top++;
                stack[top]=adj->adj_list[i].data;
            }
            e=e->next;
        }
    }
}
int main()
{
    mat_graph g;
    creatgraph(&g);
    adj_graph *adj; //二级指针
    creatadjgraph(&g,&adj);
    aov(adj);
    return 0;
}
//输出：V3->V1->V2->V6->V0->V4->V5->V8->V7->V12->V9->V10->V13->V11->